class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if(!root){
            return 0;
        }
        unsigned long long maxwidth=1;
        queue<pair<TreeNode*,unsigned long long>> q;
        q.push(make_pair(root, 1));
        while (!q.empty()) {
            maxwidth = max(maxwidth, q.back().second - q.front().second + 1);
            int len = q.size();
            for (int i = 0; i < len; i++) {
                auto node = q.front().first;
                auto index = q.front().second;
                q.pop();
                if (node->left) {
                    q.push(make_pair(node->left, index * 2));
                }
                if(node->right) {
                    q.push(make_pair(node->right, index * 2 + 1));
                }
            }
        }
        return maxwidth;
    }
};